#include "Sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void ISort(ElementType[], int, int);
static void QSort(ElementType[], int, int);
static void Swap(ElementType*, ElementType*);
static void MSort(ElementType[], ElementType[], int, int);
static void PercolateDown(ElementType[], int, int);

#define NN 20
ElementType AA[NN];

//测试排序
void TestSort() {
    for (int i = 0; i < NN; i++) {
        srand(i * 100000);
        AA[i] = rand() % 100000;
    }

    for (int i = 0; i < NN; i++) {
        printf("%d\t", AA[i]);
    }

    clock_t start, stop;
    start = clock();
    // InsertSort(AA, NN);           // 8.237s
    //  ShellSort(AA, NN);           //6.917s
    //  QuickSort(AA, NN);           // 0.011s
    //  MergeSort(AA, NN);           //0.025s
    //  HeapSort(AA, NN);            //0.016s
    //  SelectSort(AA, NN);
    BubbleSort(AA, NN);
    stop = clock();
    double time = (double)(stop - start) / CLOCKS_PER_SEC;

    printf("\n\n");
    for (int i = 0; i < NN; i++) {
        printf("%d\t", AA[i]);
    }
    printf("\n");

    printf("The time assumed is %lf s.\n", time);
}

static void Swap(ElementType* num1, ElementType* num2) {
    ElementType temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

///////////////////////////////////////////////////////////////////////////////////////////
//冒泡排序（程序优化的典范）
void BubbleSort(ElementType A[], int N) {
    /*
    //原始版本
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N - i; j++) {
            if (A[j] > A[j + 1])
                Swap(&A[j], &A[j + 1]);
        }
    }
    */

    /*
    //标记是否有序
    for (int i = 1; i < N; i++) {
        int isSorted = 1;
        for (int j = 0; j < N - i; j++) {
            if (A[j] > A[j + 1]) {
                Swap(&A[j], &A[j + 1]);
                isSorted = 0;
            }
        }
        //如果为有序，不必再进行比较
        if (isSorted)
            break;
    }
    */

    //数组右端有序
    int rightBound = N - 1;
    int lastChangePoint;
    for (int i = 1; i < N; i++) {
        int isSorted = 1;
        for (int j = 0; j < rightBound; j++) {
            if (A[j] > A[j + 1]) {
                Swap(&A[j], &A[j + 1]);
                //不能在这里给rightBound赋值，会影响循环控制变量
                lastChangePoint = j;
                isSorted = 0;
            }
        }
        rightBound = lastChangePoint;
        if (isSorted)
            break;
    }
}

///////////////////////////////////////////////////////////////////////////////////////////
//选择排序（基本无优化空间）
void SelectSort(ElementType A[], int N) {
    int min;
    for (int i = 0; i < N - 1; i++) {
        min = i;
        for (int j = i; j < N - 1; j++) {
            if (A[j + 1] < A[min])
                min = j + 1;
        }
        Swap(&A[i], &A[min]);
    }
}

///////////////////////////////////////////////////////////////////////////////////////////
//插入排序（先整体右移，最后放置）
static void ISort(ElementType A[], int N, int incre) {
    if (incre >= N - 1)
        return;

    ElementType temp;
    int i, j;
    for (i = incre; i < N; i += incre) {
        temp = A[i];
        for (j = i; j >= incre && A[j - incre] > temp; j -= incre)
            A[j] = A[j - incre];
        A[j] = temp;
    }
}

void InsertSort(ElementType A[], int N) {
    ISort(A, N, 1);
}

///////////////////////////////////////////////////////////////////////////////////////////
//希尔排序
void ShellSort(ElementType A[], int N) {
    //采用Sedgewick序列进行排序
    int incres[] = {8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1};
    for (int i = 0; i < sizeof(incres) / sizeof(int); i++)
        ISort(A, N, incres[i]);
}

///////////////////////////////////////////////////////////////////////////////////////////
//堆排序
static void PercolateDown(ElementType A[], int N, int index) {
    ElementType tempValue = A[index];
    while (2 * index + 1 < N) {
        int maxIndex = 2 * index + 1;
        if (2 * index + 2 < N && A[2 * index + 2] > A[2 * index + 1])
            maxIndex++;
        if (A[maxIndex] > tempValue) {
            A[index] = A[maxIndex];
            index = maxIndex;
        } else
            break;
    }
    A[index] = tempValue;
}

void HeapSort(ElementType A[], int N) {
    //从数组构建堆
    for (int i = N / 2 - 1; i >= 0; i--)
        PercolateDown(A, N, i);
    //排序：先交换A[0]和最后一个元素
    for (int i = N - 1; i > 0; i--) {
        Swap(&A[0], &A[i]);
        PercolateDown(A, i, 0);
    }
}

///////////////////////////////////////////////////////////////////////////////////////////
//归并排序
static void MSort(ElementType A[], ElementType tempA[], int left, int right) {
    //基准情形
    if (left >= right)
        return;

    //对子数组进行归并排序
    int center = (left + right) / 2;
    MSort(A, tempA, left, center);
    MSort(A, tempA, center + 1, right);
    //合并两个子数组
    for (int i = left; i <= right; i++)
        tempA[i] = A[i];
    int m = left, n = center + 1;
    for (int i = left; i <= right; i++) {
        if (m > center)
            A[i] = tempA[n++];
        else if (n > right)
            A[i] = tempA[m++];
        else if (tempA[m] > tempA[n])
            A[i] = tempA[n++];
        else
            A[i] = tempA[m++];
    }
}

void MergeSort(ElementType A[], int N) {
    ElementType* tempA = (ElementType*)malloc(N * sizeof(ElementType));
    MSort(A, tempA, 0, N - 1);
    free(tempA);
}

///////////////////////////////////////////////////////////////////////////////////////////
//快排排序
static void QSort(ElementType A[], int left, int right) {
    //基准情形
    if (left + 9 > right) {
        InsertSort(A + left, right - left + 1);
        return;
    }
    //采用三数中值法选取枢纽
    int center = (left + right) / 2;
    if (A[left] > A[center])
        Swap(&A[left], &A[center]);
    if (A[left] > A[right])
        Swap(&A[left], &A[right]);
    if (A[center] > A[right])
        Swap(&A[center], &A[right]);
    Swap(&A[center], &A[right - 1]);
    ElementType pivot = A[right - 1];
    //数组分割
    int m = left, n = right - 1;
    for (;;) {
        while (A[++m] < pivot) {
        }
        while (A[--n] > pivot) {
        }
        if (m < n)
            Swap(&A[m], &A[n]);
        else
            break;
    }
    Swap(&A[n], &A[right - 1]);
    //对子数组进行快排
    QSort(A, left, n - 1);
    QSort(A, n + 1, right);
}

void QuickSort(ElementType A[], int N) {
    QSort(A, 0, N - 1);
}

///////////////////////////////////////////////////////////////////////////////////////////
//计数排序
void CountSort(ElementType A[], int N) {}

///////////////////////////////////////////////////////////////////////////////////////////
//桶排序
void BucketSort(ElementType A[], int N) {}

///////////////////////////////////////////////////////////////////////////////////////////
//基数排序
void RadixSort(ElementType A[], int N) {}